package demo09StackQueue;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 10 - 18
 * Time:20:04
 */
//2.中缀表达式转为后缀表达式
//X = A + B * (C -(D + F))/E
//A B CDF+-*E/+
    //前缀：就是将运算符移到括号前面
    //前缀和后缀表达式都是没有括号的表达式
    //计算机一般对计算前缀和后缀表达式比较容易

public class Test {
    public static void main(String []args){

        String expression = "1+((2+3)*4)-5";
        List<String> expressionList = expressionToList(expression);
        System.out.println("中缀表达式转为list结构="+expressionList);
        //将中缀表达式转换为后缀表达式
        List<String> suffixList = parseToSuffixExpression(expressionList);
        System.out.println("对应的后缀表达式列表结构="+suffixList);
        //根据后缀表达式计算结果
        int calculateResult = calculate(suffixList);
        System.out.printf(expression+"=%d\n",calculateResult);
    }
    public static void main1(String []args){

        String expression = "1+((2+3)*4)-5";
        List<String> expressionList = expressionToList(expression);
        System.out.println("expressionList="+expressionList);
        //将中缀表达式转换为后缀表达式
        List<String> suffixList = parseToSuffixExpression(expressionList);
        System.out.println(suffixList);
    }

    /***
     * 1.中缀表达式转换为后缀表达式：
     * （1）使用一个stack栈结构存储操作符；使用一个List 结构存储后缀表达式结果；
     * （2）若是数字，直接存储在list中；
     * （3）当读取到左括号“（”,直接压栈
     *      当读取到元素运算符时（分两种情况）：
     *          a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时，直接入栈；
     *          b.当运算符不为空时且栈顶操作符的优先级大于或等于当前运算符的优先级时，
     *          循环执行出栈操作并加入list中，直到遇到优先级小于当前运算符的元素为止。
     *          循环执行完后再将当前运算符压栈。【只有当遇到右括号时，左括号才出栈】
     *
     *
     * （4）当遇到右括号 “ ）”时，循环执行出栈操作并加入到list中，直到遇到左括号为止，并将左括号弹出，但不加入list中；
     * （5）表达式的值读取完后，将操作符栈中的所有元素弹出并加入到list中；
     *  执行结束之后，list中存储的顺序就是我们转换后的后缀表达式的结果
     * @param expressionList
     * @return
     */
    //中缀表达式转换为后缀表达式
//    1 + ((2 + 3) * 4)- 5
    private static List<String> parseToSuffixExpression(List<String> expressionList) {
        //创建一个栈用于保存操作符
        Stack<String> opStack = new Stack<>();
        //创建一个list用于保存后缀表达式
        List<String> suffixList = new ArrayList<>();
        for(String item : expressionList){
            //得到数或操作符
            if(isOperator(item)){
                //是操作符 判断操作符栈是否为空
                if(opStack.isEmpty() || "(".equals(opStack.peek()) || priority(item) > priority(opStack.peek())){
                    //为空或者栈顶元素为左括号或者当前操作符大于栈顶操作符直接压栈
                    opStack.push(item);
                }else {
                    //否则将栈中元素出栈如队，直到遇到大于当前操作符或者遇到左括号时
                    while (!opStack.isEmpty() && !"(".equals(opStack.peek())){
                        if(priority(item) <= priority(opStack.peek())){
                            suffixList.add(opStack.pop());
                        }
                    }
                    //当前操作符压栈
                    opStack.push(item);
                }
            }else if(isNumber(item)){
                //是数字则直接入队
                suffixList.add(item);
            }else if("(".equals(item)){
                //是左括号，压栈
                opStack.push(item);
            }else if(")".equals(item)){
                //是右括号 ，将栈中元素弹出入队，直到遇到左括号，左括号出栈，但不入队
                while (!opStack.isEmpty()){
                    if("(".equals(opStack.peek())){
                        opStack.pop();
                        break;
                    }else {
                        suffixList.add(opStack.pop());
                    }
                }
            }else {
                throw new RuntimeException("有非法字符！");
            }
        }
        //循环完毕，如果操作符栈中元素不为空，将栈中元素出栈入队
        while (!opStack.isEmpty()){
            suffixList.add(opStack.pop());
        }
        return suffixList;
    }
    /**
     * 判断字符串是否为操作符
     * @param op
     * @return
     */
    public static boolean isOperator(String op){
        return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/");
    }

    /**
     * 判断是否为数字
     * @param num
     * @return
     */
    public static boolean isNumber(String num){
        return num.matches("\\d+");
    }

    /**
     * 获取操作符的优先级
     * @param op
     * @return
     */
    public static int priority(String op){
        if(op.equals("*") || op.equals("/")){
            return 1;
        }else if(op.equals("+") || op.equals("-")){
            return 0;
        }
        return -1;
    }


    /**
     * 2.将表达式转为list
     * @param expression
     * @return
     */
    private static List<String> expressionToList(String expression) {
        int index = 0;
        List<String> list = new ArrayList<>();
        do{
            char ch = expression.charAt(index);
            if(ch < 47 || ch > 58){
                //是操作符，直接添加至list中
                index ++ ;
                list.add(ch+"");
            }else if(ch >= 47 && ch <= 58){
                //是数字,判断多位数的情况
                String str = "";
                while (index < expression.length() && expression.charAt(index) >=47 && expression.charAt(index) <= 58){
                    str += expression.charAt(index);
                    index ++;
                }
                list.add(str);
            }
        }while (index < expression.length());
        return list;
    }


    //3.根据后缀表达式list计算结果
    public static int calculate(List<String> list){
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < list.size(); i++) {
            String item = list.get(i);
            if(item.matches("\\d+")){
                //是数字
                stack.push(Integer.parseInt(item));
            }else{
                //是操作符，取出栈顶两个元素
                int num2 = stack.pop();
                int num1 = stack.pop();
                int ret  = 0;
                if(item.equals("+")){
                    ret = num1 + num2;
                }else if(item.equals("-")){
                    ret = num1 - num2;
                }else if(item.equals("*")){
                    ret = num1 * num2;
                }else if(item.equals("/")){
                    ret = num1 / num2;
                }else{
                    throw new RuntimeException("运算符错误！");
                }
                stack.push(ret);
            }
        }
        return stack.pop();
    }

}
